Thư Cừ Mông Tốn sinh năm 368, song có ít tư liệu về những năm đầu đời của ông. Ông có tổ tiên Hung Nô, và tổ tiên của ông được cho là tả thư cừ (một tước quan không rõ về phận sự) của các Thiền vu Hung Nô, và do vậy họ bắt đầu dùng Thư Cừ làm họ của mình. Sau đó, dưới thời cai trị của Tiền Tần và Hậu Lương, Thư Cừ Mông Tốn được biết đến với kiến thức rộng về lịch sử và các mưu kế quân sự, bị cả thứ sử Lương Hi (梁熙) của Tiền Tần và hoàng đế Lã Quang của Hậu Lương e ngại, và do vậy ông đã cố gắng chuyển hướng chú ý của họ bằng cách uống rượu thật nhiều và dành nhiều thời gian cho những việc phù phiếm.

Năm 397, Lã Quang cử em trai Lã Diên (呂延) đi đánh Tây Tần, song Lã Diên đã rơi vào bẫy của vua Khất Phục Càn Quy của Tây Tần và bị giết chết. Các chú bác của Thư Cừ Mông Tốn là Thư Cừ La Cừu (沮渠羅仇) và Thư Cừ Khúc Chúc (沮渠麴粥) là các thuộc cấp của Lã Diên, và khi Lã Diên chết, Lã Quang đã tin vào các lời vu cáo chống lại họ rồi cho hành hình. Thư Cừ Mông Tốn hộ tống quan tài của hai người để trở về quê hương tại Trương Dịch (張掖, nay thuộc Trương Dịch, Cam Túc) và sau đó thuyết phục các bộ lạc Hung Nô khác nổi dậy chống lại Hậu Lương. Ban đầu, ông bị con trai của Lã Quang là Lã Toản đánh bại và phải chạy trốn vào các ngọn núi, song ngay sau đó ông đã hội quân cùng Thư Cừ Nam Thành (沮渠男成), người đang bao vây Kiến Khang (建康, cũng thuộc Trương Dịch ngày nay) và thuyết phục Đoàn Nghiệp (thái thú quận Kiến Khang) chấp thuận làm lãnh đạo quân nổi dậy, lập nước Bắc Lương. Ngay sau đó, Lã Quang phải đương đầu với một cuộc nổi loạn của Quách Nôn (郭黁) và đã triệu hồi Lã Toản về kinh thành đối phó, vì vậy mà đất nước non trẻ của Đoàn Nghiệp vẫn có thể tồn tại. Thư Cừ Mông Tốn gia nhập cùng Đoàn Nghiệp, và trở thành một tướng chính của đất nước. Năm 398, Đoàn Nghiệp sai ông đi chống lại một cháu trai của Lã Quang tên là Lã Chuẩn (呂純), và Thư Cừ Mông Tốn đã bắt được Lã Chuẩn, khiến cho toàn bộ các thành còn lại của Hậu Lương ở phía tây của Trương Dịch phải khuất phục trước Bắc Lương, lãnh thổ Bắc Lương vì thế tiếp tục được mở mang. Đoàn Nghiệp do đó đã phong tước hầu cho Thư Cừ Mông Tốn. Con trai của Lã Quang là Lã Hoằng (呂弘) ngay sau đó đã bỏ Trương Dịch, và Đoàn Nghiệp đã cho dời đô đến Trương Dịch và còn cố đuổi theo Lã Hoằng. Lã Hoằng đã đánh bại Đoàn Nghiệp và gần như đã giết được người này, song Thư Cừ Mông Tốn đã cứu Đoàn Nghiệp. Năm 399, khi Đoàn Nghiệp xưng là Lương vương, ông ta phong cho Thư Cừ Mông Tốn là một trong hai thừa tướng, cùng chia sẻ trách nhiệm với Lương Trung Dong (梁中庸). Cũng trong năm đó, khi Bắc Lương bị quân Hậu Lương dưới quyền chỉ huy của thái tử Lã Thiệu và Lã Toản tấn công, theo đề xuất của Thư Cừ Mông Tốn nên Đoàn Nghiệp đã không giao chiến, buộc Lã Thiệu và Lã Toản phải rút quân khi viện binh của Nam Lương do Thốc Phát Lợi Lộc Cô chỉ huy đến trợ giúp cho Bắc Lương. Năm 400, khi tướng Vương Đức (王德) nổi loạn, Đoàn Nghiệp đã sai Thư Cừ Mông Tốn đi đánh dẹp, và Thư Cừ Mông Tốn đã đánh bại được Vương Đức và khi người này chạy trốn, Thư Cừ Mông Tốn đã bắt vợ con của ông ta.

Tuy nhiên, đến năm 401, Đoàn Nghiệp rất lo ngại về các chiến lược và khả năng của Thư Cừ Mông Tốn, và ông đã tính đến việc đưa Thư Cừ Mông Tốn đến một nơi nào đó xa xôi. Thư Cừ Mông Tốn biết được sự nghi ngờ của Đoàn Nghiệp nên đã cố gắng che giấu tham vọng của mình. Tuy nhiên, vào thời gian này, do ông thường xuyên bị Mã Quyền (馬權, người mà Đoàn Nghiệp dựa vào rất nhiều) xúc phạm nên ông đã vu cáo Mã Quyền tội phản nghịch, và Đoàn Nghiệp đã cho xử tử Mã Quyền. Thư Cừ Mông Tốn sau đó bảo với Thư Cừ Nam Thành rằng Đoàn Nghiệp thiếu khả năng và không phải là một người cai trị thích hợp, và cố thuyết phục Thư Cừ Nam Thành nổi dậy chống lại Đoàn Nghiệp. Khi Thư Cừ Nam Thành từ chối, Thư Cừ Mông Tốn đã yêu cầu được rời khỏi kinh thành để làm thái thú của quận Tây An (西安, cũng thuộc Trương Dịch ngày nay), và Đoàn Nghiệp đã chấp thuận. Thư Cừ Mông Tốn sau đó lập bẫy cả Thư Cừ Nam Thành và Đoàn Nghiệp, ông hẹn với Thư Cừ Nam Thành đi tế lễ các thần thánh ở Lan Môn sơn (蘭門山, gần Trương Dịch) vào một ngày nghỉ, song lại vu cáo thông qua Hứa Hàm (許咸) rằng Thư Cừ Nam Thành định nổi loạn và sẽ khởi sự vào ngày mà ông ta thỉnh cầu được đến Lan Môn sơn tế lễ. Khi Thư Cừ Mông Tốn thỉnh cầu Đoàn Nghiệp về việc đi tế lễ, Đoàn Nghiệp đã cho bắt và lệnh cho Thư Cừ Nam Thành phải tự sát. Lúc này, Thư Cừ Nam Thành đã nhận ra được âm mưu của Thư Cừ Mông Tốn, ông ta nói với Đoàn Nghiệp rằng đây là một dấu hiệu rằng Thư Cừ Mông Tốn là quân phiến loạn và rằng hãy giữ lại mạng của ông ta để ông ta có thể chống lại cuộc nổi loạn của Thư Cừ Mông Tốn khi nó xảy ra. Đoàn Nghiệp tuy vậy vẫn không tin lời Thư Cừ Nam Thành và cho xử tử. Thư Cừ Mông Tốn sau đó đã lấy cớ Đoàn Nghiệp xử tử Thư Cừ Nam Thành để khích động dân chúng nổi loạn chống lại Đoàn Nghiệp, và dân chúng đã thực sự nổi dậy vì họ khá tôn kính Thư Cừ Nam Thành. Quân nổi loạn nhanh chóng chiếm được Trương Dịch. Bất chấp Đoàn Nghiệp van xin, Thư Cừ Mông Tốn vẫn giết chết Đoàn Nghiệp. Tất cả các quan lại của Bắc Lương đều tán thành việc Thư Cừ Mông Tốn tiếp nhận ngai vàng, và Thư Cừ Mông Tốn đã lên ngôi với tước hiệu Trương Dịch công.